package algorithm.stack;

/**
 * leetcode : https://leetcode.com/problems/longest-valid-parentheses/description/
 * Difficulty : Hard
 *
 * 最长的连续有效括号
 * 举个栗子：
 * Input : "(()"
 * Output : 2 因为最长有效括号集是 ()
 *
 * Input : ")()())"
 * Output : 4 "()()"
 *
 * Input : "())()"
 * Output : 2  因为最长的有效连续是2
 *
 *
 * 使用一个Stack的解决方案：
 * https://leetcode.com/problems/longest-valid-parentheses/discuss/14126/My-O(n)-solution-using-a-stack
 *
 * 另一个使用Stack的方案，但是更简便一些，在遇到不同的时候就计算最大值
 * https://leetcode.com/problems/longest-valid-parentheses/discuss/142776/4ms-beats-100-most-simple-C++-solution-using-stack-way
 *
 * @Author Antony
 * @Since 2018/7/11 22:43
 */
public class LongestValidParentheses {

    public static void main(String[] args) {
//        String str_1 = "(()";   // 2
//        System.out.println(longestValidParentheses_stack(str_1));
//        String str_2 = ")()())";    // 4
//        System.out.println(longestValidParentheses_stack(str_2));
        String str_3 = "()(())";    // 6
//        System.out.println(longestValidParentheses_stack_2(str_3));
//        String str_4 = "((()))())";    // 8
//        System.out.println(longestValidParentheses_stack_2(str_4));
//        String str_5 = "()(()";     // 2
//        System.out.println(longestValidParentheses_stack_2(str_5));
//        String str_6 = ")()())";    // 4
//        System.out.println(longestValidParentheses_stack_2(str_6));
//
//        String str_7 = "(()";    // 2
//        System.out.println(longestValidParentheses_stack_2(str_7));
        String str_8 = "(()()";    // 4
        System.out.println(longestValidParentheses_stack_2(str_8));

    }

    /**
     * 思路参考leetcode的小伙伴
     * 使用Stack，但是stack不是存储字符值，而是存储 遍历到的字符 在 字符串中的索引
     * 这样遇到匹配的括号就弹出，遍历完一遍以后，stack中存储的就是多出来的字符的索引
     * 就是这些索引所在的符号，分割了整段的字符串
     * 因此只要找到间隔最大的值就是我们要找的答案
     *
     * 比如遍历结束后，stack中的值为 [0,5,12],字符串长度为14
     * 那么其中完整括号的长度有 4(5-0-1) 6(12-5-1) 2(13-11-1) 那最长的就是6
     *
     * leetcode beats 99.71% - 11ms
     */
    public static int longestValidParentheses_stack(String s) {
        // 这个stack存储遍历字符串时的index
        int[] stack = new int[s.length()];
        int top = 0;
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i)==')' && top>0 && s.charAt(stack[top-1])=='('){
                top--;
            }else{
                stack[top] = i;
                top++;
            }
        }
        if(top==0){
            return s.length();
        }
        int max = 0;
        int tmpLen;
        int preIdx=-1;  //在刚开始时，假设前一个索引的值为-1，以便计算结果的正确性
        for(int i=0; i<top; i++){
            tmpLen = stack[i] - preIdx -1;
            max = max > tmpLen ? max : tmpLen;
            preIdx = stack[i];
        }

        // 最后还需要把preIdx 和 字符串末尾的差 计算一下
        tmpLen = s.length() - preIdx -1;
        max = max > tmpLen ? max : tmpLen;

        return max;
    }


    /**
     * 思路
     * 初始化 start 索引为-1, 目的是为了计算的正确性
     * 只有遇到左括号，才会往stack中放, stack中放的值, 是该左括号在string里的索引
     * 否则遇到右括号的话，如果栈已经空了，那说明该右括号是多余的 start往前移动到该位置
     *
     * leetcode beats 100.0% - 10ms
     */
    public static int longestValidParentheses_stack_2(String s) {
        int[] stack = new int[s.length()];
        int top = 0;
        // 这里要明确一点的是，如果top=0了，说明栈空了，不为0的话，栈顶元素是stack[top-1]

        int start = -1;
        int max=0, tmp;
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i)=='('){
                stack[top++] = i;
            }else if(top==0){
                start = i;
            }else{
                top--;  // 指针回退到栈顶
                if(top != 0){
                    // 如果栈非空, 由于栈顶已匹配，则取栈顶下一个的索引，该索引未匹配，而在该索引之前的以及都完全匹配.
                    // 所以要取 top-1 而不是top
                    tmp = i - stack[top-1];
                }else {
                    // 如果栈已空, 则减去上一个多余的点，即start
                    tmp = i - start;
                }
                max = max > tmp ? max : tmp;
            }
        }
        return max;
    }
}
